type graph = { nodes : int list; edges : (int * int) list }

(* Normalize edge: store (min, max) to treat (a,b) same as (b,a) *)
let normalize (a, b) = if a <= b then (a, b) else (b, a)

(* Check if (x,y) is an edge in graph g *)
let is_edge g x y =
  let norm = normalize (x, y) in
  List.mem norm (List.map normalize g.edges)

(* Check if current partial mapping f preserves adjacency for all mapped pairs *)
let consistent g1 g2 f =
  let dom = List.map fst f in
  let for_all_pairs lst =
    List.for_all (fun x ->
      List.for_all (fun y ->
        if x = y then true else
          let adj1 = is_edge g1 x y in
          try
            let x' = List.assoc x f in
            let y' = List.assoc y f in
            let adj2 = is_edge g2 x' y' in
            adj1 = adj2
          with Not_found -> true (* if either not mapped, skip *)
      ) lst
    ) lst
  in
  for_all_pairs dom

(* Backtracking search for isomorphism *)
let rec iso_rec g1 g2 f unmapped1 unmapped2 =
  match unmapped1 with
  | [] -> true  (* all nodes mapped, and consistency already checked *)
  | x :: rest ->
      List.exists (fun y ->
        let f' = (x, y) :: f in
        if consistent g1 g2 f' then
          iso_rec g1 g2 f' rest (List.filter ((<>) y) unmapped2)
        else
          false
      ) unmapped2

(* Main isomorphism function *)
let iso g1 g2 =
  if List.length g1.nodes <> List.length g2.nodes then false
  else if List.length g1.edges <> List.length g2.edges then false
  else
    let n1 = List.sort compare g1.nodes in
    let n2 = List.sort compare g2.nodes in
    iso_rec g1 g2 [] n1 n2

let g = { nodes = [1; 2; 3; 4; 5; 6; 7; 8];
edges = [(1,5); (1,6); (1,7); (2,5); (2,6); (2,8); (3,5);
          (3,7); (3,8); (4,6); (4,7); (4,8)] };;

let h = { nodes = [1; 2; 3; 4; 5; 6; 7; 8];
  edges = [(1,2); (1,4); (1,5); (6,2); (6,5); (6,7); (8,4);
            (8,5); (8,7); (3,2); (3,4); (3,7)] };;

iso g h;;  (* Should return true *)